This invention relates to a machine-implemented method of and device for circle generation. More particularly, it pertains to a circle-generation employing a digital differential analyzer algorithm.
In fields such as computer graphics, computer-controlled printing, and computer-aided design it is frequently necessary to generate circles and circular arcs by calculating coordinates representing a consecutive sequence of points on the circle or arc. One method for generating such circles and arcs that is described, for example, on pages 27 and 28 of Principles of Interactive Computer Graphics by Newman Sproull, published by McGraw-Hill, employs the general class of algorithms known as digital differential analyzers (hereinafter denoted DDA). The basic DDA circle-generation algorithm is derived from the differential equation of a circle centered at the origin of the coordinate system: ##EQU2## The discrete form of this equation is the difference equation (2): ##EQU3## in which x.sub.n and y.sub.n are the coordinates of the n-th point on the circle, x.sub.n+1 and y.sub.n+1 are the coordinates of the (n+1)-th point on the circle, and n is zero or a positive integer.
Solutions to equation (2) have the following form: EQU x.sub.n+1 =x.sub.n +.epsilon.y.sub.n EQU y.sub.n+1 =y.sub.n -.epsilon.x.sub.n ( 3)
If the circle or arc will be displayed on a raster device in which coordinates are expressed in integer pixel counts, and if the radius of curvature r of the circle or arc falls in the range: EQU 2.sup.(m-1) .ltoreq.r&lt;2.sup.m ( 4)
then the value of .epsilon. should be 2.sup.-m to prevent the spacing between successive points from exceeding the distance between pixels. Making .epsilon. a negative power of 2 facilitates implementation of the algorithm in a computing device by allowing right shifts to be substituted for multiplications.
The basic DDA circle-generation algorithm can be conveniently expressed by rewriting equation (3) as the matrix equation (5), in which the vector [x.sub.n y.sub.n ] represents the n-th point on the circle and the vector [x.sub.n+1 y.sub.n+1 ] represents the (n+1)-th point. The algorithm calculates [x.sub.n+1 y.sub.n+1 ] from [x.sub.n y.sub.n ] by performing matrix multiplication: ##EQU4##
A problem with this algorithm is that the determinant of its matrix exceeds unity: ##EQU5## A consequence is that this algorithm plots not a true circle but a spiral in which successive points are disposed successively farther from the origin. If a complete circle is plotted, the starting point fails to coincide with the ending point.
A prior-art solution to this problem given in the reference cited above is to compute y.sub.n+1 from x.sub.n+1 instead of x.sub.n. The preceding solution (3) is then modified as follows: EQU x.sub.n+1 =x.sub.n +.epsilon.y.sub.n EQU y.sub.n+1 =y.sub.n -.epsilon.x.sub.n+1 ( 6)
A DDA circle-generation algorithm according to (6) can be expressed by the matrix equation (7): ##EQU6## The matrix in this equation has a determinant of unity: ##EQU7## Accordingly, successive points do not spiral outward, and if a complete circle is plotted, the starting and ending points coincide. However, the result is still not a true circle, because the algorithm shown in equation (7) is derived by altering the differential equation (1) to equation (8): ##EQU8## Equation (8) does not describe a circle. As pointed out in the reference cited above, the departure from circularity may be quite large for large values of .epsilon..